package com.ztom.top100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 每日温度
 * <p>
 * https://leetcode-cn.com/problems/daily-temperatures/
 *
 * @author ZhangTao
 */
public class Code100DailyTemperatures {

    public int[] dailyTemperatures(int[] temperatures) {
        if (temperatures == null || temperatures.length == 0) {
            return null;
        }

        int[] res = new int[temperatures.length];
        // 记录下标
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peekLast()] < temperatures[i]) {
                Integer top = stack.pollLast();
                res[top] = i - top;
            }
            stack.offerLast(i);
        }
        // 栈内没有结算的, 说明右侧没有大值, 默认为 0
        return res;
    }
}
